1. Field of the Invention
This invention relates generally to hard disk error correction code decoders, and more particularly to devices for generating error location polynomials using Reed-Solomon error correction code technique.
2. Description of the Related Art
Modern computer systems typically include one or more hard disk drives to store large amount of data and programs. As a mass storage circuitry, hard disk drives can provide information to the processors in the computer systems through random access memory (RAM) circuitry such as dynamic random access memory (DRAM), static random access memory (SRAM), etc. Since RAM circuitry is costly, storing information in a hard disk and retrieving the information as needed is generally far more economical than using comparable RAM circuitry for most computer applications.
Hard disk drives typically store information as sequential bits using magnetic technology. Like most recording technology, reading the sequential data bits from a hard disk often generates errors due to noise, manufacturing imperfections of the physical medium, dust, etc. To detect and correct such errors, hard disk drives typically implement an error correction code (ECC) scheme in writing to and reading from hard disk drives.
A typical ECC scheme computes ECC bytes for a given block of user data such as a sector. Then, computed ECC bytes are appended to a block of user data and then recorded on a hard disk. When the block of data is read, the ECC scheme computes error locations and error patterns in the user data by decoding the ECC bytes.
Prior Art FIG. 1 illustrates a block diagram of a conventional computer system 100 including a host computer 118 that receives data from a disk 102 in a hard disk drive. A motor 104 spins the disk 102 containing the data. A read/write head 106 attached to an actuator 108 searches for a track and sectors that contain the desired data. Upon finding the desired sectors, the read/write head 106 reads the data sequentially from the disk 102. An amplifier 110 amplifies the data signals and transmits the amplified data signals to an analog-to-digital converter 112. The analog-to-digital converter 112 converts the amplified data signals into digital data bits and transmits the data bits to a deserializer 114. The deserializer 114 receives the sequential data bits and converts the data into a series of blocks called sectors, each of which is typically 512 bytes of user data and ECC bytes appended to the user data bytes. The deserializer 114 sequentially transmits the sectors to an error detection and correction (EDAC) circuitry 116, which detects errors in the received sector and, if correctable, corrects the detected errors using an ECC scheme. The EDAC circuitry 116 then transmits the error corrected user data to the host computer 118.
Prior Art FIG. 2 shows a more detailed block diagram of the EDAC circuitry 116. As mentioned above, the EDAC circuitry 116 receives a sector 200 of user data bytes and ECC bytes in sequential manner. At the front end of the EDAC circuitry 116, a syndrome generator 202 receives the sector 200 and generates partial syndromes from the received sector data. Syndrome generators are well known in the art and are typically implemented as a linear feedback shift register circuit. The generated partial syndrome indicates whether an error is present in the received sector 200. For example, a zero syndrome indicates that no error has been detected. On the other hand, a non-zero syndrome indicates that one or more errors has been detected in the received data.
With continued reference to Prior Art FIG. 2, the generated partial syndromes are then transmitted to an ECC decoder 204, which includes error locator polynomial generator 206, an error locator polynomial solver 208, and an error pattern generator 210. The error locator polynomial generator 206 receives the partial syndromes from the syndrome generator 202 and generates an error locator polynomial for the received sector 200. Using the error locator polynomial, the error locator polynomial solver computes the error locations in the received sector and transmits the error locations to th error pattern generator 210. The error pattern generator 21 computes error patterns in the received sector 200 using the error locations and partial syndromes. The EDAC uses the error locations and error patterns to correct the errors in the received sector.
One of the most robust hard disk ECC scheme employs conventional Reed-Solomon code to encode user data for reliable recovery of the original data. Modern hard disk drives generally employ Reed-Solomon error correcting code (ECC) for burst error correction to help achieve higher areal density. A Reed-Solomon code is completely defined by a generator polynomial, g(z), whose zeroes are consecutive powers of field elements of Galois Field, GF(q): .alpha..sup.m.sbsp.0, .alpha..sup.m.sbsp.0.sup.+1, . . . , .alpha..sup.m.sbsp.0.sup.+c-1, where m.sub.0 is defined between 0 and q-2 (i.e., 0.ltoreq.m.sub.0 .ltoreq.q-2) and c is the number of checkbytes. The vector form of the received sector is represented as (r.sub.0, r.sub.1, . . . , r.sub.n-1). Assuming that a block length n code and .nu. errors occurred in locations corresponding to indexes i.sub.1, i.sub.2, . . . , i.sub..nu., the partial syndromes are defined by a partial syndrome equation as follows: ##EQU1## According to equation (1), the error location number for position i.sub.k is defined to be .alpha..sup.i.sbsp.k. The syndrome components define a series of c algebraic equations with 2.nu. unknowns.
Assuming .LAMBDA.(z) is an error locator polynomial that has its roots the inverses of the .nu. error locators {.alpha..sub.ik }, the error locator polynomial .LAMBDA.(z) can be expressed as: ##EQU2## A key equation relating the partial syndromes to the error locator polynomial may be defined as: EQU .LAMBDA..sub..nu. S.sub.j-.nu. +.LAMBDA..sub..nu.-1 S.sub.j-.nu.+1 +. . . +.LAMBDA..sub.1 S.sub.j-1 =-S.sub.j (3)
Based on this relationship, when partial syndromes S.sub.j are given, conventional Berlekamp-Massey algorithm can be used to find the polynomial .LAMBDA.(z) of minimum degree .nu. so that key equation (3) is satisfied.
The Berlekamp-Massey algorithm has five basic parameters: the connection polynomial .LAMBDA..sup.(k) (z), the correction polynomial T(z), the discrepancy .DELTA..sup.(k), the number of coefficients or errors, L, that is to be detected (e.g., length of a shift register), and the indexing variable k. Berlekamp-Massey algorithm and Reed-Solomon code are well known in the art and is amply described in Error Control Systems for Digital Communication and Storage, ISBN 0-13-200809-2(1995), by Stephen B. Wicker, which is incorporated herein by reference.
Prior Art FIG. 3 illustrates a flow diagram 300 of the operations involved in a conventional Berlekamp-Massey algorithm after receiving partial syndromes in the form of syndrome sequence S.sub.1, . . . , S.sub.c for a received sector data at the c zeros where c is the number of checkbytes as mentioned above. The Berlekamp-Massey algorithm implements Berlekamp's algorithm for decoding nonbinary BCH and Reed-Solomon codes using Massey's shift-register-based interpretation.
In operation 302, the Belekamp-Massey algorithm initializes variables k, .LAMBDA., L, and T: k=0, .LAMBDA..sup.(0) (z)=1, L=0, and T(z)=z. Then in operation 304, the index variable k is incremented by 1 and the discrepancy .DELTA..sup.(k) is computed as follows: ##EQU3## In operation 306, the algorithm determines whether .DELTA..sup.(k) =0. If .DELTA..sup.(k) is equal to zero, the algorithm proceeds to operation 316 where T(z) is set equal to z T(z). On the other hand, if .DELTA..sup.(k) is not equal to zero, the algorithm proceeds to operation 308 where the value of .LAMBDA..sup.(k) (z) is determined in accordance with an equation .LAMBDA..sup.(k) (z)=.LAMBDA..sup.(k-1) (z)-.DELTA..sup.(k) T(z).
Then in operation 310, the algorithm determines whether the value of 2L is greater than or equal to k. If the value of 2L is greater than or equal to k, then the algorithm proceeds to operation 316. On the other hand, if 2L is smaller than k, then the algorithm proceeds to set L=k-L in operation 312.
Subsequently in operation 314, T(z) is computed according to an equation T(z)=.LAMBDA..sup.(k-1) (z)/.DELTA..sup.(k). Following this, T(z) is set as T(z)=z T(z) in operation 316, which has the effect of incrementing the degree of polynomial T(z) by a degree. Then in operation 316, the algorithm determines if k is smaller than c, the number of checkbytes. If k is not smaller than c, the algorithm terminates in operation 320. Otherwise, the algorithm proceeds back to operation 304. When the algorithm 300 terminates in operation 320, the algorithm 300 provides an error locator polynomial, .LAMBDA.(z)=.LAMBDA..sup.(c) (z), whose coefficients indicate the location of errors, if any, in the block of data such as a sector.
Unfortunately, the implementation of the Berlekamp-Massey algorithm typically requires many clock cycles which are dependent on a result from previous cycles. Furthermore, straight forward implementation of Berlekamp-Massey algorithms generally requires numerous storage elements and Galois Field (GF) multipliers, which are major datapath resources requiring a large silicon area.
In view of the foregoing, what is needed is an apparatus and method that can efficiently compute error locator polynomial .LAMBDA.(z) by implementing Berlekamp-Massey algorithm in reduced clock cycles. What is further needed is an apparatus and method that utilizes less storage elements and GF multipliers, and thus less silicon area.